package everyday;

import java.util.Arrays;

/**
 * @Author: Siantar
 * @Date: 2023-06-12-21:15
 * @Description: 1.0
 */
public class T1483 {
    class TreeAncestor {
        static final int LOG = 16;
        int[][] ancestors;

        public TreeAncestor(int n, int[] parent) {
            ancestors = new int[n][LOG];
            for (int i = 0; i < n; i++) {
                Arrays.fill(ancestors[i], -1);
            }
            for (int i = 0; i < n; i++) {
                ancestors[i][0] = parent[i];
            }
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < LOG; j++) {
                    if (ancestors[i][j - 1] != -1) {
                        ancestors[i][j] = ancestors[ancestors[i][j - 1]][j - 1];
                    }
                }
            }
        }

        public int getKthAncestor(int node, int k) {
            for (int i = 0; i < LOG; i++) {
                if (((k >> i) & 1) == 1) {
                    node = ancestors[node][i];
                }
                if (node == -1) {
                    return -1;
                }
            }
            return node;
        }
    }
}